package exampleQuestions;

public class LinkedListSum {
	
	static class Node {
		int digit;
		Node next;
		
		public Node(int v) {
			this.digit = v;
		}
	}
	
	static class Result {
		Node n;
		int transfer;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// 15674
		Node node1 = new Node(9);
		Node node2 = new Node(5);
		node1.next = node2;
		Node node3 = new Node(6);
		node2.next = node3;
		Node node4 = new Node(7);
		node3.next = node4;
		Node node5 = new Node(4);
		node4.next = node5;

		// 4767
		Node node9 = new Node(4);
		Node node6 = new Node(7);
		node9.next = node6;
		Node node7 = new Node(6);
		node6.next = node7;
		Node node8 = new Node(7);
		node7.next = node8;
		
		Node n = sumLists(node9, node1);
		
		print(n);
		
	}
	
	private static Node sumLists(Node n1, Node n2) {
		
		int l1 = getLength(n1);
		int l2 = getLength(n2);
		
		Result result = sum(l1 - l2, n1, n2);
		if (result != null) {
			Node n = result.n;
			if(result.transfer > 0) {
				n = new Node(result.transfer);
				n.next = result.n;
			}
			return n;
		} else return null;
	}

	private static Result sum(int i, Node n1, Node n2) {
		if(i != 0) {
			Result res2 = null;
			if(i >0) {
				Result res = sum(i-1, n1.next, n2);
				
				res2 = sum(res, n1, new Node(0));
			} else {
				Result res = sum(i+1, n1, n2.next);
				res2 = sum(res, new Node(0), n2);
			}
			
			return res2;
		} else {
			if (n1 != null) {
				Result res = sum(i, n1.next, n2.next);
				Result res2 = sum(res, n1, n2);
				
				return res2;
			} else {
				return null;
			}
		}
	}

	private static Result sum(Result res, Node n1, Node n2) {
		
		Node n = new Node(0);
		if(res == null) {
			res = new Result();
			res.n = new Node(0);
			n.next = null;
		} else {
			n.next = res.n;
		}
		
		n.digit = n1.digit + n2.digit + res.transfer;
		Result r = new Result();
		r.n = n;
		r.transfer = n.digit / 10;
		n.digit %= 10;
		
		return r;
	}

	private static int getLength(Node node) {
		int length = 0;
		while (node != null) {
			length++;
			node = node.next;
		}
		return length;
	}

	private static void print(Node head) {
		if (head != null) {
			System.out.print(head.digit);
			print(head.next);
		}
	}

}
